#include <stdio.h>
#include <stdlib.h>

// 分块结构体
struct Block
{
    int max;   // 块内最大值
    int start; // 块起始索引
    int end;   // 块结束索引
};

// 分块查找函数
int block_search(int arr[], int size, struct Block blocks[], int block_num, int target)
{
    // 1. 先在块索引中确定可能存在的块
    int target_block = -1;
    for (int i = 0; i < block_num; i++)
    {
        if (target <= blocks[i].max)
        { // 找到第一个max大于等于target的块
            target_block = i;
            break;
        }
    }

    if (target_block == -1)
    {
        return -1; // 所有块的max都小于target，目标不存在
    }

    // 2. 在确定的块内进行线性查找
    for (int i = blocks[target_block].start; i <= blocks[target_block].end; i++)
    {
        if (arr[i] == target)
        {
            return i; // 找到目标
        }
    }

    return -1; // 块内未找到
}

int main()
{
    // 测试数组（部分有序，适合分块查找）
    int data[] = {3, 8, 10, 15, 20, 22, 25, 30, 32, 40, 45, 50, 55, 60};
    int size = sizeof(data) / sizeof(data[0]);

    // 定义分块（3个块）
    int block_num = 3;
    struct Block blocks[3] = {
        {15, 0, 3}, // 第1块：最大值15，索引0-3
        {30, 4, 7}, // 第2块：最大值30，索引4-7
        {60, 8, 13} // 第3块：最大值60，索引8-13
    };

    // 情况1：查找成功（在第1块）
    int target1 = 10;
    int result1 = block_search(data, size, blocks, block_num, target1);

    if (result1 != -1)
    {
        printf("Element %d found at index %d.\n", target1, result1); // 输出查找成功信息
    }
    else
    {
        printf("Element %d not found in the array.\n", target1);
    }

    // 情况2：查找成功（在第3块）
    int target2 = 50;
    int result2 = block_search(data, size, blocks, block_num, target2);

    if (result2 != -1)
    {
        printf("Element %d found at index %d.\n", target2, result2);
    }
    else
    {
        printf("Element %d not found in the array.\n", target2);
    }

    // 情况3：查找失败（值在范围内但不存在）
    int target3 = 28;
    int result3 = block_search(data, size, blocks, block_num, target3);

    if (result3 != -1)
    {
        printf("Element %d found at index %d.\n", target3, result3);
    }
    else
    {
        printf("Element %d not found in the array.\n", target3); // 输出查找失败信息
    }

    // 情况4：查找失败（值超出范围）
    int target4 = 65;
    int result4 = block_search(data, size, blocks, block_num, target4);

    if (result4 != -1)
    {
        printf("Element %d found at index %d.\n", target4, result4);
    }
    else
    {
        printf("Element %d not found in the array.\n", target4); // 输出查找失败信息
    }

    return 0;
}